Programmable logic devices (PLDs) are integrated circuits (ICs) that are used to implement digital logic operations according to user configurable input. Example PLDs include Complex Programmable Logic Devices (CPLDs) and field programmable gate arrays (FPGAs). CPLDs often include several function blocks that are based on programmable logic array (PLA) architecture with sum-of-products logic. A configurable interconnect matrix transmits signals between the function blocks.
An example FPGA includes an array of configurable logic blocks (CLBs) and a ring or columns of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure (routing resources). The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and interconnect structure are configured. The configuration bitstream may be read from an external memory, conventionally an external integrated circuit memory EEPROM, EPROM, PROM, and the like, though other types of memory may be used. The collective states of the individual memory cells determine the function of the FPGA. A specific type of FPGA uses a look-up-table (LUT)-based CLB. The configuration memory provides input values to a number of multiplexers controlled by inputs to the CLB.
A conventional design process for an integrated circuit, such as an ASIC or an FPGA begins with the creation of the circuit design. The function of a circuit design may be represented using various programmable languages (e.g., VHDL, ABEL or Verilog) or schematic capture programs. The design is logically synthesized to produce a logical network list (“netlist”) supported by the target integrated circuit device. The netlist is mapped to primitive components that are available within a target device (e.g., a target programmable IC).
Following logical synthesis, components of the netlist are placed for implementation within the target device. During placement, each mapped component of the design is assigned to a physical position on the chip where an instance of the corresponding primitive component may be found. The purpose of the placer is to place connected design objects in close physical proximity to one another. This conserves space on the chip and increases the probability that the desired interconnections between components will be successfully completed by the router. Placing connected components close to one another also generally improves the performance of the circuit, since long interconnect paths are associated with excess capacitance and resistance, resulting in longer delays.
Specified connections between components of the design are routed within the target device for the placed components. Routing specifies physical wiring resources that will be used to conduct signals between pins of placed components of the design. For each connection specified in the design, routing must allocate wiring necessary to complete the connection. As used herein, the selection and assignment of wire resources in connecting the output pin of one component to the input pin of another component is referred to as routing a signal. When signals have been routed using most or all of the wiring resources in a given area, the area is generally referred to as congested, which creates competition for the remaining wiring resources in the area or makes routing of additional signals in the area difficult or impossible. Place-and-route procedures sometimes involve optimization of a design's timing, power consumption, routing resources utilized, and any combination thereof. In some instances, timing-based estimations of the design are also provided.